package leetcode;

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 1) {
            return Arrays.asList("()");
        }

        Set<String> set = new HashSet<>();

        for (String str : generateParenthesis(n - 1)) {
            for (int i = 0; i <= str.length() / 2; i++) {
                set.add(str.substring(0, i) + "()" + str.substring(i, str.length()));
            }
        }

        return new ArrayList<>(set);
    }
}

public class Test3 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.generateParenthesis(3);
    }
}
